#include<stdio.h>
#include<string.h>
#include<mpi.h>
#define MAX_LATTICE_DIMENSION 1000
#define DEBUG 0

/*
* Temporary variable for KMP algorithm
*/
char T[50];

/*
* Stores the dimension of the Lattice
*/
int LATTICE_DIMENSION;
int NUM_WORDS_DICT;
int WORD_LENGTH_DICT;

/*
 lattice: 
	This variable store the lattice in the memory for quick access and forming the word patterns for matching
 */
char ***lattice;	
/* dictionary :
	This variable stores the words in the dictionary in memory */
char *dictionary[100];



int main(int argc, char *argv[]){


	if ( argc != 5 ) /* argc should be 2 for correct execution */
	    {
		/* We print argv[0] assuming it is the program name */
		printf( "usage: %s -dict DICTIONARY_NAME -input LATTICE_FILE", argv[0] );
	    }
	    else 
	    {
		// We assume argv[1] is a filename to open
		FILE *file = fopen( argv[1], "r" );

		/* fopen returns 0, the NULL pointer, on failure */
		if ( file == 0 )
		{
		    printf( "Could not open file\n" );
		}
		else 
		{
		    int x;
		    /* read one character at a time from file, stopping at EOF, which
		       indicates the end of the file.  Note that the idiom of "assign
		       to a variable, check the value" used below works because
		       the assignment statement evaluates to the value assigned. */
		    while  ( ( x = fgetc( file ) ) != EOF )
		    {
			printf( "%c", x );
		    }
		    fclose( file );
		}
	    }	





	/**
	* Variables for MPI version of the Lattice program
	* 	numprocs: Number of processors
	*	rank: The id of the current process under execution
	*/
	int numprocs, rank, namelen;

	/* Initialize MPI */	  
	MPI_Init(&argc, &argv);
	
	/* Get the size of the global communicator and the rank of the current process */
	MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	int i=0;
	int j=0;
	int k=0;
	/*
	* Input the lattice filename which contains the list of words in the 3D lattice in csv
	* @TODO change this as an command line argument to the program?
	*/ 
	char *filename = "input2.txt";
	/*
	* The name of the dictionary file which contains csv values of the words
	* @TODO change this as an command line argument to the program?
	*/	
	char *dict_file = "dict1.txt";
	
	/**
	* The current version of the code uses dictionary of size 100
	* @TODO We assume there are three words only for now (simplicity). Need to generalize this
	*/
	dictionary[0] = "";
	dictionary[1] = "";
	dictionary[2] = "";
	
	/**
	* Read the dictionary file and load the contents to the dictionary variable
	*/
	readDictionary(dict_file);
	
	/**
	* Read the lattice dimension. This is obtained by the wordlength of the first word in the input file.
	* @TODO Need to validate this with other words and throw error otherwise!
	*/
	readLatticeDimension(filename);
	
	/*
	* allocate memory according to the LATTICE_DIMENSION
	*/

	lattice = (char ***)malloc(LATTICE_DIMENSION * sizeof(char **));	
	for(i=0;i< LATTICE_DIMENSION; i++){
	   lattice[i] = (char **) malloc(LATTICE_DIMENSION * sizeof(char *));
	   for(j=0;j<LATTICE_DIMENSION; j++)
		  lattice[i][j] = (char *) malloc(LATTICE_DIMENSION * sizeof(char));
	}	
	
	
	/**
	* Read the lattice into memory
	*/
	readLattice(filename, lattice);		
	
	/**
	* load the dictionary file into memory
	*/
	loadDictionary(dict_file, dictionary);		
	
	//displayLattice(lattice);	
	
	//Start of the algorithm
	
	/*********************************************
	This version of the code uses straight forward algorithm of searching for a pattern within a given string.
	Steps:
		1. Given a 3D Lattice, obtain a planar face
		2. Get the set of dictionary words to be searched.
		3. For each face:
			a. form the set of horizontal, vertical and diagonal words from the lattice face
			b. Search for each of the pattern in the set of words
		4. For each character in the planar face
			a. Obtain the 3D diagonals
				For each character there could possibly be four 3-D diagonals maximum, depending on the location of the character.
			b. Search for each of the pattern in the set of 3D diagonal words.
		5. End the program with Yes if any of the patterns in the dictionary have been found, else return No.	
	
	For searching we use Knuth Morris Pratt.
	***********************************************/
 
	/**
	* wordptr
	* Variable pointing to a word in the dicitonary
	*/
	int wordptr;

	char _mpi_sendbuf[WORD_LENGTH_DICT * NUM_WORDS_DICT], _mpi_recvbuf[WORD_LENGTH_DICT+1];
        //printf("I am process %d\n", rank);
	if(rank ==0)
	{
		_mpi_sendbuf[0] = '\0';
		for(wordptr = 0; wordptr < NUM_WORDS_DICT; wordptr++)
		{
		//	printf("\nmpi_sendbuf=%s - %s\n", _mpi_sendbuf, dictionary[wordptr]);
			strcpy(_mpi_sendbuf,strcat(_mpi_sendbuf, dictionary[wordptr]));	
		} 
		//printf("_mpi_sendbuf=%s,\n", _mpi_sendbuf);
	}
	MPI_Scatter(_mpi_sendbuf,WORD_LENGTH_DICT, MPI_CHARACTER,_mpi_recvbuf, WORD_LENGTH_DICT,MPI_CHARACTER, 0, MPI_COMM_WORLD);
	_mpi_recvbuf[WORD_LENGTH_DICT]='\0'; 
	doSearch(_mpi_recvbuf);
	printf("\n\n\n\ Searching %s %d\n\n\n", _mpi_recvbuf, rank );
	MPI_Finalize();
}

/**
* Implementation of the search algorithm
*/
void doSearch(char word[]){
		int i=0, j=0, k=0;
		char *currentWord = word;		
		/**
		* This stores the word sequence in the Y direction for each planar set of words
		*/
		char *lattSeqY;
		/**
		* This stores the word sequence in the X direction for each planar set of words
		*/		
		char *lattSeqX;
		/**
		* This stores the word sequence in the Z direction for each planar set of words
		*/				
		char *lattSeqZ;
		
		/**
		* Each planar face is assumed to be made up of two major diagonals, diag1 and diag2
		* The complementary diagonals based on them are diag1Dash and diag2Dash respectively.
		*/				
		char *diag1, *diag1Dash;
		char *diag2, *diag2Dash;

		/**
		* Each planar face is assumed to be made up of two major 3D diagonals, diag3D1 and diag3D2
		* The complementary diagonals based on them are diag3D1Dash and diag3D2Dash respectively.
		*/						
		char *diag3D1, *diag3D1Dash;
		char *diag3D2, *diag3D2Dash;
		
		
		/**
		* Memory allocation 
		* Based in LATTICE_DIMENSION. Size of each variable is LATTICE_DIMENSION.
		*/				
		
		lattSeqY = (char *) malloc(LATTICE_DIMENSION * sizeof(char));		
		lattSeqZ = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		lattSeqX = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		diag1 = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		diag2 = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		diag1Dash = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		diag2Dash = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		
		diag3D1 = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		diag3D2 = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		diag3D1Dash = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		diag3D2Dash = (char *) malloc(LATTICE_DIMENSION * sizeof(char));	
		
		for(i= 0; i< LATTICE_DIMENSION; i++)
			for(j=0;j<LATTICE_DIMENSION; j++){
				
				/**
				* Variable initialization
				*/
				lattSeqY[0] = '\0';
				lattSeqZ[0] = '\0';
				lattSeqX[0] = '\0';
				diag1[0] = '\0';
				diag2[0] = '\0';
				diag1Dash[0] = '\0';
				diag2Dash[0] = '\0';

				diag3D1[0] = '\0';
				diag3D2[0] = '\0';
				diag3D1Dash[0] = '\0';
				diag3D2Dash[0] = '\0';
				
				for(k=0;k<LATTICE_DIMENSION; k++){
					char temp[2], temp1[2], temp2[2];
					char tempD1[2], tempD2[2];
					char tempD1Dash[2], tempD2Dash[2];
					
					temp[0] = lattice[k][j][i];
					temp[1] = '\0';
					lattSeqY = strcat(lattSeqY, temp); 					
					
					if(j+k < LATTICE_DIMENSION){
						tempD1[0] = lattice[k][j+k][i];
						tempD1[1] = '\0';
						
						tempD1Dash[0] = lattice[j+k][k][i];
						tempD1Dash[1] = '\0';
						
						diag1 = strcat(diag1, tempD1);
						diag1Dash = strcat(diag1Dash, tempD1Dash);
					}
					
					if(j-k >= 0 && j-k < LATTICE_DIMENSION){
						tempD2[0] = lattice[k][j-k][i];						
						tempD2[1] = '\0';
						tempD2Dash[0] = lattice[j-k][k][i];
						tempD2Dash[1] = '\0';											
						diag2 = strcat(diag2, tempD2);
						diag2Dash = strcat(diag2Dash, tempD2Dash);
					}		
																
					temp1[0] = lattice[i][j][k];
					temp1[1] = '\0';
					lattSeqZ = strcat(lattSeqZ, temp1); 					
					
					temp2[0] = lattice[k][i][j];
					temp2[1] = '\0';
					lattSeqX = strcat(lattSeqX, temp2); 												
					
					// for 3D diagonals
					int l =0;
					char temp3D1[2], temp3D2[2];
					char temp3D1Dash[2], temp3D2Dash[2];
					diag3D1[0] = lattice[k][j][i];
					diag3D1[1] = '\0';
					diag3D1Dash[0] = lattice[k][LATTICE_DIMENSION - 1- j][i];
					diag3D1Dash[1] = '\0';					
					
					diag3D2[0] = lattice[k][j][i];
					diag3D2[1] = '\0';
					diag3D2Dash[0] = lattice[k][LATTICE_DIMENSION - 1- j][i];
					diag3D2Dash[1] = '\0';							
					for(l=1;l< LATTICE_DIMENSION; l++){		
						
						if(k+l < LATTICE_DIMENSION && j+l < LATTICE_DIMENSION && i+l < LATTICE_DIMENSION){
							temp3D1[0] = lattice[k+l][j+l][i+l];
							temp3D1[1] = '\0';
							diag3D1 = strcat(diag3D1, temp3D1);					
							temp3D1Dash[0] = lattice[k + l][LATTICE_DIMENSION - 1 - j - l][ i + l];													
							temp3D1Dash[1] = '\0';							
							diag3D1Dash = strcat(diag3D1Dash, temp3D1Dash);	
						}
						
						if(k-l >= 0 && j-l >= 0 && i-l >=0 && j+l < LATTICE_DIMENSION){
							temp3D1[0] = lattice[k-l][j-l][i-l];						
							temp3D1[1] = '\0';
							diag3D1 = strcat( diag3D1, temp3D1);	
							
							 temp3D1Dash[0] = lattice[k-l][LATTICE_DIMENSION -1 - j + l][i - l];
							 temp3D1Dash[1] = '\0';
							 diag3D1Dash = strcat(diag3D1Dash, temp3D1Dash);								
						}
						
						// @TODO Check 3D diagonals
						// Above diagonals seem to be working fine, however the implementation below of the other 3D diagonal is buggy. It doesn't yield the diagonals of correct length.							
						
						// if(k-l >= 0 &&j-l >=0 && i+l < LATTICE_DIMENSION && j+l < LATTICE_DIMENSION ){
							// temp3D2[0] = lattice[k-l][j-l][i+l];
							// temp3D2[1] = '\0';
							// diag3D2 = strcat(temp3D2, diag3D2);					
						
							// temp3D2Dash[0] = lattice[k - l][j + l][ i + l];							
							// temp3D2Dash[1] = '\0';							
							// diag3D2Dash = strcat(diag3D2Dash, temp3D2Dash);	
						// }
						
						// if(k+l < LATTICE_DIMENSION && j+l < LATTICE_DIMENSION && j-l >=0 && i-l >=0){
							// temp3D2[0] = lattice[k+l][j+l][i-l];
							// temp3D2[1] = '\0';
							// diag3D2 = strcat(diag3D2, temp3D2);					
						
							// temp3D2Dash[0] = lattice[k + l][j - l][ i - l];							
							// temp3D2Dash[1] = '\0';							
							// diag3D2Dash = strcat(diag3D2Dash, temp3D2Dash);	
						// }
					}
					
					//printf("\n\t3D Diag = %s, start = %c, DiagD1 = %s, Diag2 =%s, Diag2D=%s", diag3D1, lattice[k][j][i], diag3D1Dash, diag3D2, diag3D2Dash);
					
					if(strlen(diag3D1)>1){
						printf("\nSearching for [%s] in [%s] 3D Diagonal", currentWord, diag3D1);
						kmp_table(currentWord, diag3D1, WORD_LENGTH_DICT, LATTICE_DIMENSION);
						kmp(currentWord, diag3D1, WORD_LENGTH_DICT, LATTICE_DIMENSION);					
					}
					
					// if(strlen(diag3D2)>1){
						// printf("\nSearching for [%s] in [%s] 3D Diagonal", currentWord, diag3D2);
						// kmp_table(currentWord, diag3D2, WORD_LENGTH_DICT, LATTICE_DIMENSION);
						// kmp(currentWord, diag3D2, WORD_LENGTH_DICT, LATTICE_DIMENSION);					
					// }						
					
					if(strlen(diag3D1Dash)>1){
						printf("\nSearching for [%s] in [%s] 3D Diagonal", currentWord, diag3D1Dash);
						kmp_table(currentWord, diag3D1Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);
						kmp(currentWord, diag3D1Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);					
					}
					
					// if(strlen(diag3D2Dash)>1){
						// printf("\nSearching for [%s] in [%s] 3D Diagonal", currentWord, diag3D2Dash);
						// kmp_table(currentWord, diag3D2Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);
						// kmp(currentWord, diag3D2Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);					
					// }										
				}

	
				printf("\nSearching for [%s] in [%s]", currentWord, lattSeqY);
				kmp_table(currentWord, lattSeqY, WORD_LENGTH_DICT, LATTICE_DIMENSION);
				kmp(currentWord, lattSeqY, WORD_LENGTH_DICT, LATTICE_DIMENSION);
				
				printf("\nSearching for [%s] in [%s]", currentWord, lattSeqZ);
				kmp_table(currentWord, lattSeqZ, WORD_LENGTH_DICT, LATTICE_DIMENSION);
				kmp(currentWord, lattSeqZ, WORD_LENGTH_DICT, LATTICE_DIMENSION);

				printf("\nSearching for [%s] in [%s]", currentWord, lattSeqX);
				kmp_table(currentWord, lattSeqX, WORD_LENGTH_DICT, LATTICE_DIMENSION);
				kmp(currentWord, lattSeqX, WORD_LENGTH_DICT, LATTICE_DIMENSION);
				
				if(strlen(diag1) >= 2 ){		
					printf("\nSearching for [%s] in [%s] diagonal", currentWord, diag1);
					kmp_table(currentWord, diag1, WORD_LENGTH_DICT, LATTICE_DIMENSION);
					kmp(currentWord, diag1, WORD_LENGTH_DICT, LATTICE_DIMENSION);		

					printf("\nSearching for [%s] in [%s] diagonal", currentWord, diag1Dash);
					kmp_table(currentWord, diag1Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);
					kmp(currentWord, diag1Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);							
				}
				
				
				if(strlen(diag2) >= 2 ){
						int dFlag = 0;
						char tempD2Dash[2];						
						
						//if(strcmp(diag2, strrev(diag2Dash)) == 0){
						if(strcmp(diag2, Reverse(diag2Dash)) == 0){
						
							// select the alternative diagonal (The diagonal in the lower half of the matrix)							 
							diag2Dash[0] = '\0';
							tempD2Dash[0] = '\0';
							for(k=0;k<LATTICE_DIMENSION; k++){								
								//tempD2[0] = lattice[k][j-k][i];					
								if(k<(j+1)){
									tempD2Dash[0] = lattice[LATTICE_DIMENSION - 1 - j + k][LATTICE_DIMENSION - 1 - k][i];	
									tempD2Dash[1] = '\0';
									diag2Dash = strcat(diag2Dash, tempD2Dash);
								}							
							}							
							dFlag=1;
						}				
					printf("\nSearching for [%s] in [%s] diagonal", currentWord, diag2);
					kmp_table(currentWord, diag2, WORD_LENGTH_DICT, LATTICE_DIMENSION);
					kmp(currentWord, diag2, WORD_LENGTH_DICT, LATTICE_DIMENSION);				
					
					printf("\nSearching for [%s] in [%s] diagonal dFlag=%d", currentWord, diag2Dash, dFlag);
					kmp_table(currentWord, diag2Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);
					kmp(currentWord, diag2Dash, WORD_LENGTH_DICT, LATTICE_DIMENSION);							
				}				
			}
			printf("\n");
}

/*
* Read the dictionary to get the values for 
* NUM_WORDS_DICT - Number of words in the dictionary
* WORD_LENGTH_DICT - The length of each word in the dictionary. This is given in the requirement specs. to be of the same 	* length
*/

void readDictionary(char filename[]){
   FILE *file = fopen ( filename, "r" );
   char *pch;
   if ( file != NULL )
   {
	  // @TODO change this limit to include the requirement MAX_WORDS = 1000, and MAX_WORD_LENGTH=100
      char line [ 128 ]; /* or other suitable maximum line size */
      fgets ( line, sizeof line, file ); /* read a line */
	  pch = strtok (line,",");
	  WORD_LENGTH_DICT = strlen(pch);
	  if(DEBUG)
	  printf("Dictionary word length = %d\n", WORD_LENGTH_DICT);	  
		 while (pch != NULL){			
			NUM_WORDS_DICT++;
			pch = strtok (NULL,",");
		 }	  
	  fclose ( file );
	  if(DEBUG)
	  printf("No. of words = %d\n", NUM_WORDS_DICT);
   }
   else
   {
      perror ( filename ); /* why didn't the file open? */
   }
}

/*
* load the words from the dictionary file into the array dictionary
*/

void loadDictionary(char filename[], char *dictionary[100]){
   FILE *file = fopen ( filename, "r" );
   char *pch;
   int wordi = 0;
   int l=0;
   if ( file != NULL )
   {
	  // @TODO change this limit to include the requirement MAX_WORDS = 1000, and MAX_WORD_LENGTH=100
      char line [ 128 ]; /* or other suitable maximum line size */
	  
      fgets ( line, sizeof line, file ); /* read a line */
	  pch = strtok (line,",");
		 while (pch != NULL){
			//dictionary[wordi] = "";
			//dictionary[wordi] = pch;
			dictionary[wordi] = (char *)malloc(WORD_LENGTH_DICT * sizeof(char));			
			strcpy(dictionary[wordi], pch);
			wordi++;			
			pch = strtok (NULL,",");		
			
		 }	  
		 
	  fclose ( file );
   }
   else
   {
      perror ( filename ); /* why didn't the file open? */
   }
}

void displayLattice(char ***lattice){
	int i,j,k;
	for(i= 0; i< LATTICE_DIMENSION; i++){
		for(j=0;j<LATTICE_DIMENSION; j++)
		{
			for(k=0;k<LATTICE_DIMENSION; k++)
				printf("%c\t", lattice[k][j][i]);
			printf("\n");
		}
		printf("\n");
	}
}


int readLatticeDimension(char filename[]){
   /* 
	* Read the dimension of the lattice.
    */
   FILE *file = fopen ( filename, "r" );
   char *pch;
   if ( file != NULL )
   {
      char line [ 128 ]; /* or other suitable maximum line size */
      fgets ( line, sizeof line, file ); /* read a line */
	  pch = strtok (line,",");
	  LATTICE_DIMENSION = strlen(pch);
	  if(DEBUG)
	  printf("Lattice dimension = %d\n", LATTICE_DIMENSION);
	  fclose ( file );
   }
   else
   {
      perror ( filename ); /* why didn't the file open? */
   }
}


/*
* Read the lattice and store the strings in a multidimensional array
* input - filename of the lattice
* output - load the input 
*/
int readLattice (char filename[], char ***lattice)
{   
   int charIndex = 0;
   int lineNo = 0;
   int i = 0; 
   int j = 0;
   
   FILE *file = fopen ( filename, "r" );   
   char *pch;
   
   file = fopen ( filename, "r" );
   if ( file != NULL )
   {
      char line [ 128 ]; /* or other suitable maximum line size */
	  int wordIndex = 0;
      while ( fgets ( line, sizeof line, file ) != NULL ) /* read a line */
      {
		 pch = strtok (line,",");
		 wordIndex = 0;
		 while (pch != NULL){			
			//printf("%s\t", pch);
			for(charIndex = 0; charIndex < LATTICE_DIMENSION; charIndex++)
			{
				lattice[charIndex][wordIndex][lineNo] = (char)pch[charIndex];
				//printf("%c\t", lattice[lineNo][charIndex][0]);
			}
			wordIndex++;
			pch = strtok (NULL,",");
		 }		 
         //fputs ( line, stdout ); /* write the line */
		 lineNo++;
      }	  
      fclose ( file );
   }
   else
   {
      perror ( filename ); /* why didn't the file open? */
   }		
   return 0;
}


/* Checks whether a given pattern is present in the 
*
*/

int checkPatternX(char pattern[], char ***lattice){

}

/*
* Implementation of Knuth Morris Pratt Algorithm
* Inspired from http://www.daniweb.com/software-development/c/threads/83793
* Input 
*    *ptr_i = Pointer to the start of the word to be found
*    *ptr_m = Pointer to the start of the sentence which needs to be checked 
*    word_length = length of the word
*    sentence_length = length of the entire sentence
*/

kmp(char *ptr_i,char *ptr_m,int word_length,int sentence_length)
{
  int pos,m=0,i=0;
  for(;m<sentence_length; )
    {
      if(*(ptr_i+i) == *(ptr_m+m+i))
        {
          i=i+1;
			if(i==word_length)
			 {
			   pos=m+1;
			   printf("\nThe word was found at position %d\n",pos );
			   printf("\n\n FOUND = Yes");
			   exit(0);
			 }
        }
       else
        { 
			 m=m+i-T[i];
			 if(i>0)
				i=T[i]; 
        }
    } 
      return sentence_length;
}

/*
* Knuth Morris Pratt Algorithm initialization step
* Inspired from http://www.daniweb.com/software-development/c/threads/83793
* Input 
*    *ptr_i = Pointer to the start of the word to be found
*    *ptr_m = Pointer to the start of the sentence which needs to be checked 
*    word_length = length of the word
*    sentence_length = length of the entire sentence
*/
 
 
kmp_table(char *ptr_i,char *ptr_m,int word_length,int sentence_length)
{
	 int i,j;
	  i=2;
	  j=0;
	  T[0]=-1;
	  T[1]=0;
	  for(;i<word_length; )
	  {
			if(*(ptr_i+i-1) == *(ptr_i+j))
			   {
				T[i]=j+1;
				i=i+1;
				j=j+1;
			   }
	 
			else if(j>0)
				{
				 j=T[j];
				}
	 
			else
				{
				 T[i]=0;
				 i=i+1;
				}
	 } 
}

/*
* In case strrev is not supported, We use this function
* taken from http://cboard.cprogramming.com/c-programming/3603-trying-not-use-strrev-function.html
* @TODO check the correctness of the function
*/

void Reverse(char* pData)
{
    int Length=strlen(pData);                
    char* last=pData+Length-1;//last char before null
    while (pData<last) // stops at midpoint
        {
            *pData^=*last;
            *last^=*pData;
            *pData^=*last;
            ++pData;
            --last;             
        }
	return pData;
}
